package com.wj.algorithm.lintcode;

import java.util.ArrayList;
import java.util.List;

public class P118 {

    List<String> getRemaind(String s, char target, int tIndex, int sLen, int tLen) {
        List<String> list = new ArrayList<String>();
        
        int maxSIndex = sLen - (tLen - tIndex - 1);
        
        for(int scan = 0; scan < maxSIndex; scan ++) {
            char scanCh = s.charAt(scan);
            if(scanCh == target) {
                list.add(s.substring(scan + 1));
            }
        }
        
        return list;
    }
    
    public int numDistinct(String S, String T) {
        
        int tLen = T.length();
        
        int tIndex = 0;
        List<String> temp = new ArrayList<String>();
        temp.add(S);
        
        while(temp.size() > 0 && tIndex < tLen) {

            List<String> list = new ArrayList<String>();

            for(String s : temp) {
                List<String> newTemp = getRemaind(s, T.charAt(tIndex), tIndex, s.length(), tLen);
                if(newTemp != null) {
                    list.addAll(newTemp);
                }
            }
            tIndex ++;
            temp = list;
        }
        
        return temp.size();
    }
    
    public static void main(String[] args) {
        String S = "aabdbaabeeadcbbdedacbbeecbabebaeeecaeabaedadcbdbcdaabebdadbbaeabdadeaabbabbecebbebcaddaacccebeaeedababedeacdeaaaeeaecbe";
        String T = "bddabdcae";
        
        System.out.println(new P118().numDistinct(S, T));
    }
}
